package com.fyt.recover.order;

import java.util.Arrays;

import java.util.Arrays;

public class HeapSort {
    // 调整以 s 为根的大根堆（0-based 索引）
    public static void heapAdjust(int[] arr, int s, int m) {
        int max = arr[s]; // 保存根节点值
        for (int j = 2 * s + 1; j <= m; j = 2 * j + 1) { // 左子节点索引
            if (j < m && arr[j] < arr[j + 1]) j++; // 选出左右子节点中较大的
            if (max >= arr[j]) break; // 若根节点比最大子节点还大，结束调整
            arr[s] = arr[j]; // 把较大子节点上移
            s = j;  // 继续向下调整
        }
        arr[s] = max; // 把原根节点值放入最终位置
    }

    // 创建大根堆
    public static void createHeap(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) { // 从最后一个非叶子节点开始调整
            heapAdjust(arr, i, n - 1);
        }
    }

    // 堆排序
    public static void sort(int[] arr) {
        createHeap(arr); // 先建堆
        for (int i = arr.length - 1; i > 0; i--) {
            // 交换堆顶（最大值）和最后一个元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 重新调整剩余部分为大根堆
            heapAdjust(arr, 0, i - 1);
        }
        System.out.println("排序后数组: " + Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("原始数组: " + Arrays.toString(arr));

        sort(arr);

        System.out.println("排序后数组: " + Arrays.toString(arr));
    }
}
